package com.xjh.basestudy.lanqiaobei;
/**
 * 差分数组通常用于高效地进行区间更新操作，比如在数组的某个区间加上一个值。
 *
 * 初始化差分数组：
 * 1.创建差分数组：差分数组 diff 的长度通常比原数组 a 多1（防止区间右边界操作越界）。
 * 2.构造初始差分值（若原数组初始值不为0）
 * 区间修改操作
 * 1. 定义修改方法：对区间 [l, r] 内的所有元素增加（或减少）值 val。
 * 重构最终数组
 * 1.通过前缀和还原：从差分数组 diff 生成最终的数组 a。
 *
 *
 场景	    前缀和 (Prefix Sum)	    差分数组 (Difference Array)
 核心功能	快速查询区间和 sum[l..r]	高效区间修改 add[l..r]
 * */
public class Chafen {
    public static void main(String[] args) {
        // 原始数组（初始全为0）
        int[] a = new int[10];

        // 差分数组（比原数组多1个元素）
        int[] diff = new int[a.length + 1];

        // 初始差分数组构造（当初始数组全0时可以跳过）
        // diff[0] = a[0];
        // for (int i = 1; i < a.length; i++) {
        //     diff[i] = a[i] - a[i-1];
        // }

        // 示例1：在区间 [2, 5] 增加3
        addRange(diff, 2, 5, 3);

        // 示例2：在区间 [0, 7] 增加5
//        addRange(diff, 0, 7, 5);
//
//        // 示例3：在区间 [3, 9] 减少2
//        addRange(diff, 3, 9, -2);

        // 通过差分数组重构最终数组
        reconstruct(a, diff);

        // 输出结果
        System.out.print("差分数组：");
        for (int num : diff) {
            System.out.print(num + " ");
        }
        System.out.println();
        System.out.print("最终数组：");
        for (int num : a) {
            System.out.print(num + " ");
        }
    }

    // 区间增加操作 [l, r]
    static void addRange(int[] diff, int l, int r, int val) {
        diff[l] += val;
        diff[r + 1] -= val;  // 利用多出的最后一个元素防止越界
    }

    // 通过差分数组重构原始数组（前缀和）
    static void reconstruct(int[] a, int[] diff) {
        a[0] = diff[0];  // 初始值
        for (int i = 1; i < a.length; i++) {
            a[i] = a[i - 1] + diff[i];
        }
    }
}
